package day190707;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/7/7 上午 11:00
 */
public class DelNodes {
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        List<TreeNode> result = new ArrayList<>();
        boolean deleteRoot = false;
        for (int value : to_delete) {
            if (value == root.val) {
                deleteRoot = true;
            }
            deleteNode(root, value, result);
        }
        if (deleteRoot) {
            result.add(root);
        }
        for (Iterator<TreeNode> iterator = result.iterator(); iterator.hasNext(); ) {
            TreeNode treeNode = iterator.next();
            if (treeNode.val == -1) {
                iterator.remove();
                continue;
            }
            deleteNodeForNull(treeNode);
        }
        return result;
    }

    private boolean deleteNode(TreeNode root, int toDelete, List<TreeNode> result) {
        if (root == null) {
            return false;
        }
        if (root.val == toDelete) {
            if (root.left != null) {
                result.add(root.left);
            }
            if (root.right != null) {
                result.add(root.right);
            }
            return true;
        } else {
            if (deleteNode(root.left, toDelete, result)) {
                root.left.val = -1;
            }
            if (deleteNode(root.right, toDelete, result)) {
                root.right.val = -1;
            }
            return false;
        }
    }

    private void deleteNodeForNull(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null && root.left.val == -1) {
            root.left = null;
        }
        if (root.right != null && root.right.val == -1) {
            root.right = null;
        }
        if (root.left != null) {
            deleteNodeForNull(root.left);
        }
        if (root.right != null) {
            deleteNodeForNull(root.right);
        }
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        if (x == 1) {
            return true;
        }
        TreeNode rootX = find(root, x);
        int num = getChildNum(rootX.left) + getChildNum(rootX.right);
        if (num > n - num) {
            return false;
        }else {
            return true;
        }
    }

    private int getChildNum(TreeNode rootX) {
        if (rootX.left != null) {
            return getChildNum(rootX.left) + 1;
        }
        if (rootX.right != null) {
            return getChildNum(rootX.right) + 1;
        }
        return 0;
    }

    private TreeNode find(TreeNode root, int x) {
        if (root.val == x) {
            return root;
        }
        if (root.left != null) {
            TreeNode left = find(root.left, x);
            if (left != null) {
                return left;
            }
        }
        if (root.right != null) {
            TreeNode right = find(root.right, x);
            if (right != null) {
                return right;
            }
        }
        return null;
    }
}
